package com.LeeCode;

import java.util.*;

/**
 * 祖玛游戏
 */

public class Code488 {
    public static void main(String[] args) {
        Code488 solution = new Code488();

        // 测试用例
        System.out.println(solution.findMinStep("WRRBBW", "RB"));      // 输出: -1
        System.out.println(solution.findMinStep("WWRRBBWW", "WRBRW")); // 输出: 2
        System.out.println(solution.findMinStep("G", "GGGGG"));        // 输出: 2
        System.out.println(solution.findMinStep("RBYYBBRRB", "YRBGB")); // 输出: 3
    }

    Map<String, Integer> dp = new HashMap<String, Integer>();

    public int findMinStep(String board, String hand) {
        char[] arr = hand.toCharArray();
        Arrays.sort(arr);
        hand = new String(arr);
        int ans = dfs(board, hand);
        return ans <= 5 ? ans : -1;
    }

    public int dfs(String board, String hand) {
        if (board.length() == 0) {
            return 0;
        }
        String key = board + " " + hand;
        if (!dp.containsKey(key)) {
            int res = 6;
            for (int j = 0; j < hand.length(); ++j) {
                // 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同
                if (j > 0 && hand.charAt(j) == hand.charAt(j - 1)) {
                    continue;
                }
                for (int i = 0; i <= board.length(); ++i) {
                    // 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球
                    if (i > 0 && board.charAt(i - 1) == hand.charAt(j)) {
                        continue;
                    }

                    // 第 3 个剪枝条件: 只在以下两种情况放置新球
                    boolean choose = false;
                    //  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同
                    if (i < board.length() && board.charAt(i) == hand.charAt(j)) {
                        choose = true;
                    }
                    //  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球
                    if (i > 0 && i < board.length() && board.charAt(i - 1) == board.charAt(i) && board.charAt(i - 1) != hand.charAt(j)) {
                        choose = true;
                    }

                    if (choose) {
                        String newBoard = clean(board.substring(0, i) + hand.charAt(j) + board.substring(i));
                        String newHand = hand.substring(0, j) + hand.substring(j + 1);
                        res = Math.min(res, dfs(newBoard, newHand) + 1);
                    }
                }
            }
            dp.put(key, res);
        }
        return dp.get(key);
    }

    public String clean(String s) {
        StringBuffer sb = new StringBuffer();
        Deque<Character> letterStack = new ArrayDeque<Character>();
        Deque<Integer> countStack = new ArrayDeque<Integer>();

        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            while (!letterStack.isEmpty() && c != letterStack.peek() && countStack.peek() >= 3) {
                letterStack.pop();
                countStack.pop();
            }
            if (letterStack.isEmpty() || c != letterStack.peek()) {
                letterStack.push(c);
                countStack.push(1);
            } else {
                countStack.push(countStack.pop() + 1);
            }
        }
        if (!countStack.isEmpty() && countStack.peek() >= 3) {
            letterStack.pop();
            countStack.pop();
        }
        while (!letterStack.isEmpty()) {
            char letter = letterStack.pop();
            int count = countStack.pop();
            for (int i = 0; i < count; ++i) {
                sb.append(letter);
            }
        }
        sb.reverse();
        return sb.toString();
    }

    class State {
        String board;
        String hand;
        int step;

        public State(String board, String hand, int step) {
            this.board = board;
            this.hand = hand;
            this.step = step;
        }

    }
}


